#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int getUglyNumber(int n) {
        if (n <= 1) return n;
        vector<int> f(1, 1);
        int i = 0, j = 0, k = 0;
        long long t = 0;
        while (--n)
        {
            t = min(f[i] * 2, min(f[j] * 3, f[k] * 5));
            if (t == f[i] * 2) i++;
            if (t == f[j] * 3) j++;
            if (t == f[k] * 5) k++;
            f.push_back(t);
        }
        return f.back();
    }
};